package Leetcode.DayTest;

import java.util.*;

/**
 * @ClassName Test_423
 * @since: 2024/11/10 10:28
 * @auth: kirito
 * @description: 周赛423
 **/
public class Test_423 {
    public static void main(String[] args) {
        Test_423 test = new Test_423();
        List<Integer> list = new ArrayList<>(Arrays.asList(-9,9,-6,-5,6,9));
        System.out.println(test.maxIncreasingSubarrays(list));
    }
    public boolean hasIncreasingSubarrays(List<Integer> nums, int k) {
        int n = nums.size();

        for (int i = 0; i <= n - 2 * k; i++) {

            boolean flag = true;
            for (int j = i; j < i + k - 1; j++) {
                if (nums.get(j) >= nums.get(j + 1)) {
                    flag = false;
                    break;
                }
            }
            // 如果第一个子数组不是严格递增的，跳过后续检查
            if (!flag) {
                continue;
            }

            // 检查从位置i+k开始的长度为k的子数组是否严格递增
            boolean secondIncreasing = true;
            for (int j = i + k; j < i + 2 * k - 1; j++) {
                if (nums.get(j) >= nums.get(j + 1)) {
                    secondIncreasing = false;
                    break;
                }
            }
            // 如果两个子数组都是严格递增的，返回true
            if (flag && secondIncreasing) return true;
        }

        return false;
    }

    /**
     * 给你一个由 n 个整数组成的数组 nums ，请你找出 k 的 最大值，使得存在 两个 相邻 且长度为 k 的 严格递增 子数组。具体来说，需要检查是否存在从下标 a 和 b (a < b) 开始的 两个 子数组，并满足下述全部条件：
     *
     * 这两个子数组 nums[a..a + k - 1] 和 nums[b..b + k - 1] 都是 严格递增 的。
     * 这两个子数组必须是 相邻的，即 b = a + k。
     * 返回 k 的 最大可能 值。
     *
     * 子数组 是数组中的一个连续 非空 的元素序列。
     *
     * 示例 1：
     *
     * 输入：nums = [2,5,7,8,9,2,3,4,3,1]
     *
     * 输出：3
     *
     * 解释：
     *
     * 从下标 2 开始的子数组是 [7, 8, 9]，它是严格递增的。
     * 从下标 5 开始的子数组是 [2, 3, 4]，它也是严格递增的。
     * 这两个子数组是相邻的，因此 3 是满足题目条件的 最大 k 值。
     *
     */

    public int maxIncreasingSubarrays(List<Integer> nums) {
        int n = nums.size();
        if (n < 2) return 0; // 如果数组长度小于2，不可能有两个相邻的子数组
        int[] arr = new int[n];
        //记录从当前位置开始的最长的递增长度
        Arrays.fill(arr, 1);
        for (int i = n - 2; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                if (nums.get(i) < nums.get(j)) {
                    arr[i] = Math.max(arr[i], 1 + arr[j]);
                }
                break;
            }
        }

        int maxK = 0;
        /*
        超时了，然后我就在思考，哪里会影响呢，觉得这个k的遍历的话，能否加快一点k的遍历呢
        就想到了二分，k的O(n)就变成了log n  就通过了，无敌！！！
        for (int k = 1; k <= n / 2; k++) { // k的最大值最多为数组长度的一半
            boolean found = false;
            for (int i = 0; i + 2 * k <= n; i++) { // i 是第一个子数组的起点
                if (arr[i] >= k && arr[i + k] >= k) {
                    found = true;
                    break;
                }
            }
            if (found) {
                maxK = k;
            } else {
                break; // 如果当前k找不到，更大的k也不可能找到
            }
        }

         */
        int left = 1, right = n / 2;
        while (left <= right) {
            int k = left + (right - left) / 2;
            boolean found = false;
            for (int i = 0; i + 2 * k <= n; i++) { // i 是第一个子数组的起点
                if (arr[i] >= k && arr[i + k] >= k) {
                    found = true;
                    break;
                }
            }
            if (found) {
                maxK = k;
                left = k + 1;
            } else {
                right = k - 1;
            }
        }

        return maxK;
    }



}
